package org.example.sort;

import org.example.utils.ArrayUtils;

/**
 * 类描述：堆排序
 * <br>
 *
 * @author ZS
 * @version 1.0
 * @date 2020/12/28
 **/
public class HeapSort {

    /**
     * 进行堆排序（原地）：按从小到大排序
     *
     * @param arr
     * @return
     */
    public int[] sort(int[] arr) {
        if (arr == null) {
            throw new IllegalArgumentException("传入的数组不能为null");
        }

        // 构建大根堆
        initHeap(arr, arr.length);

        int len = arr.length - 1;
        // 在大根堆的基础上进行原地排序
        while (len > 0) {
            // 交换大堆顶和末尾的元素值
            ArrayUtils.swap(arr, 0, len);
            // 对剩下的长度进行大根堆的向下调整
            heapify(arr, 0, --len);
        }
        return arr;
    }

    /**
     * 构建大根堆
     *
     * @param arr 数组
     * @param len 数组中有效元素的数组
     */
    private void initHeap(int[] arr, int len) {
        // 最后一个非叶子结点的索引
        int lastNonLeaf = (len - 2) >> 1;
        while (lastNonLeaf >= 0) {
            heapify(arr, lastNonLeaf--, len);
        }
    }

    /**
     * 大根堆：对堆顶元素进行一次整理
     *
     * @param arr  数组
     * @param root 根结点
     * @param len  数组中有效元素的个数
     */
    private void heapify(int[] arr, int root, int len) {
        // 获取左子结点
        int left = (root << 1) + 1;
        // 根结点、左子结点、右子节点中最大的值
        int maxIndex = root;

        // 获取
        while (left < len) {
            // 如果左子结点大于根结点的值
            if (arr[left] > arr[maxIndex]) {
                maxIndex = left;
            }
            // 如果右子节点存在且值大与左子结点和根结点
            if (left + 1 < len && arr[left + 1] > arr[maxIndex]) {
                maxIndex = left + 1;
            }
            if (root != maxIndex) {
                // 如果根结点不是最大值，交换两个结点的值，并更新相关的值
                ArrayUtils.swap(arr, maxIndex, root);
                root = maxIndex;
                left = (root << 1) + 1;
            } else {
                // 如果根结点为最大值，忽略跳过
                break;
            }
        }
    }

}
